package com.zhj.algorithm.sort;

import java.util.Arrays;

/**
 * @PackageName:com.zhj.algorithm.sort
 * @ClassName:HeapSort
 * @auter: 朱慧杰
 * @date:2020/8/10 0010 16:09
 **/
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = new int[]{9,6,8,7,0,1,10,4,2};
        System.out.println("原来的数据：" + Arrays.toString(arr));

        /*int start = (arr.length-1)/2;
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }

        System.out.println("第一个大顶堆：" + Arrays.toString(arr));*/

        heapSort(arr);

        System.out.println("排好序的数据：" + Arrays.toString(arr));

    }

    public static void heapSort(int[] arr) {

        // 开始位置是最后一个非叶子节点，及最后一个节点的父节点
        int start = (arr.length-1)/2;

        // 调整为大顶堆
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }

        for (int i = arr.length-1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            maxHeap(arr, i, 0);
        }

    }

    public static void maxHeap(int[] arr, int size, int index) {
        // 找到两个节点
        int leftNode = 2 * index + 1;
        int rightNode = 2 * index + 2;
        int max = index;
        // 和两个子节点分别对比，找出最大节点
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }
        // 交换位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            
            // 可能会破坏，之前排好的堆
            maxHeap(arr, size, max);
        }

    }

}
